package main

import "runtime"

func main() {
	array := []int{2, 4, 5, 1, 3, 123, 8, 234, 3, 56, 1, 123, 312, 452, 34}
	insertionSort(array)
}

// 最好 n，最差和平均都是 n^2，稳定

// 插入排序，就是从第二个开始，跟前面的比较，是否小于，就插到他的前面。实现的时候注意，比他大的都得往后移一位
func insertionSort(array []int) {
	n := len(array)
	for i := 1; i < n; i++ {
		current := array[i]
		j := i - 1
		for j >= 0 && array[j] > current {
			array[j+1] = array[j]
			j--
		}
		array[j] = current
	}
	runtime.Breakpoint()
}
